The present invention concerns the encrypting and the decrypting of data within a computing system and pertains specifically to memory configurations which support use of multiple cryptographic algorithms.
In order to protect against theft or misuse, secure information within a computing system can be encrypted before being transferred over a network or other medium. When received, the secure information is decrypted before being used. The RSA cryptographic algorithm and the Diffie-Hellman cryptographic algorithm are examples of public key algorithms that utilize both public and private key components to perform key exchanges. Each of these cryptographic algorithms requires private components that are programmed into the system memory.
For example, in the Diffie-Hellman algorithm, all users in the computing system agree on a common large prime number n, and second number g, such that g is primitive mod n. The selected values for n and g are not kept secret. Each user in the system then generates a large random integer x, which is the private key. The associated public key, X, is generated the following formula: EQU X=g.sup.x mod n
Two users can compute a shared secret key, k, by exchanging public keys, X and Y and applying the following formula: EQU k=Y.sup.x mod n EQU k'=X.sup.y mod n
where EQU k=k'=g.sup.xy mod n
Unlike the Diffie-Hellman algorithm, which is a key exchange algorithm, the RSA cryptographic algorithm does not require users to belong to a "system" and have knowledge of predetermined values. Each user determines his own public and private key pairs. To do this two randomly generated large prime numbers p and q are kept secret. The two randomly generated large prime numbers p and q are used to generate a public key n according to the following formula: EQU n=p*q
The numbers p and q are also, along with a public key component e, used to generate a private key d which also must be kept secret. The formula used to generate private key d is as follows: EQU d=e.sup.-1 mod((p-1)(q-1)).
To encrypt a message m to produce an encrypted message c, the sender would use the receivers public key in the following formula: EQU c=m.sup.e mod n
To decrypt the encrypted message c to produce the original message m, the receiver would use his private key in the following formula: EQU m=c.sup.d mod n.
The various key components can be stored in a one time programmable memory (OTP) in a computer system allowing permanent access within the system. This also facilitates the ability of a computer system to provide some protection against undesired copying of the key components from an integrated circuit chip on which the key components are stored.
For example, for the Diffie-Hellman algorithm, the private key, x, is stored in 512 bits of a one-time programmable memory. This number is kept private. The same one-time programmable memory can also be used to store the large prime number n and the second number g. For example, 512 bits of the one-time programmable memory are used to store the number n and 32 bits of the one-time programmable memory are used to store the number g.
In order to support 1024 bit RSA cryptographic algorithm, the length of the value p and of the value q are half the 1024 bit length of n. Thus the values p and q are each 512 bits in length and are each stored using 512 bits in memory. Additionally, the public key component e is also stored using 32 bits of memory. It is advantageous to store p and q rather than storing the secret key d in memory. This is because it is computationally faster to perform the exponentiations utilizing the Chinese Remainder Theorem which use p and q rather than using d.
For additional information on the RSA Algorithm and the Diffie-Hellman algorithm, see Bruce Schneier, Applied Cryptography, John Wiley & Sons, Inc., 1996, pp. 466-469, 513-514.